/*
 * Sort.h
 *
 * Created 6/13/2009 By Johnny Huynh
 *
 * Version 00.00.01 6/13/2009
 *
 * Copyright Information:
 * All content copyright © 2009 Johnny Huynh. All rights reserved.
 */
 
 template <typename TYPENAME> static void my_sort( TYPENAME * const a, size_t size );
 template <typename TYPENAME> inline void my_partial_sort( TYPENAME * const a, size_t r, size_t g, size_t end );
 template <typename TYPENAME> void quicksort( TYPENAME *arrayPtr, size_t start, size_t end );
 template < typename TYPENAME > size_t partition( TYPENAME *arrayPtr, size_t start, size_t end );
 template < typename TYPENAME > void swap( TYPENAME &element1, TYPENAME &element2 );
 template < typename TYPENAME > void heapSort(TYPENAME* numbers, size_t array_size);
 template < typename TYPENAME > void siftDown(TYPENAME* numbers, size_t root, size_t bottom);
 template < typename TYPENAME > void binary_heapsort(TYPENAME* a, size_t array_size);
 template < typename TYPENAME > void binary_siftdown(TYPENAME* a, size_t root, size_t bottom);
 template < typename TYPENAME > void tertiary_heapsort(TYPENAME* a, size_t array_size);
 template < typename TYPENAME > void tertiary_siftdown(TYPENAME* a, size_t root, size_t bottom);
 template < typename TYPENAME > void biquadratic_heapsort(TYPENAME* a, size_t array_size);
 template < typename TYPENAME > void biquadratic_siftdown(TYPENAME* a, size_t root, size_t bottom);
 
 #include "introsort.h"
 #include <ctime>
 #include <cassert>
 #include <algorithm>
 
 #ifndef SORT_TEST_TYPE
 #define SORT_TEST_TYPE 0
 #endif // SORT_TEST_TYPE

 #if SORT_TEST_TYPE == 0
 // i = number of numbers to generate and sort
 template < typename TYPENAME >
 void test_sort( void(*func)( TYPENAME * const a, size_t size ), int i )
 {
    std::vector<int> v;
    
    srand( (unsigned int) time( NULL ) );
    //int i = 100000;
    
    while ( i > 0 )
    {
        v.push_back( rand() );
        --i;
    }
    
    /*printf("Before Sort\n");
    printf("Begin Vector\n");
    for ( int i = 0x0; i < v.size(); ++i )
    {
        printf("%1d ", v[i]);
    }
    printf("\nEnd Vector\n");*/
    
    printf("Begin\n");
    clock_t beginTime = clock();
    
    //sort( v.begin(), v.end(), compare );
    //quicksort( &v[0], 0, v.size() - 1 );
    //heapSort( &v[0], v.size() );
    //my_sort( &v[0], v.size() );
    //introsort( &v[0], v.size() );
    func( &v[0], v.size() );
    
    clock_t endTime = clock();
    std::cout << "TIME: " << (endTime - beginTime) /*/ CLOCKS_PER_SEC*/ << " seconds" << std::endl;
    printf("\nDone\n");
    
    /*printf("After Sort\n");
    printf("Begin Vector\n");
    for ( size_t i = 0x0; i < v.size(); ++i )
    {
        printf("%1d ", v[i]);
    }
    printf("\nEnd Vector\n");*/
    
    for ( size_t i = 0x0; i < v.size() - 1; ++i )
    {
        //assert( v[i] <= v[i + 1] );
        if ( v[i] > v[i + 1] )
        {
            printf("%1d ", v[i]);
            printf("%1d ", v[i+1]);
            system("PAUSE");
        }
    }
    printf("\nsize: %1d\n", v.size());
 }
 #endif // SORT_TEST_TYPE == 0
 
 #if SORT_TEST_TYPE == 1
 // i = number of numbers to generate and sort
 template < typename TYPENAME >
 void test_sort( void(*func)( TYPENAME * const a, size_t size, bool(*compare)(const TYPENAME&, const TYPENAME&) ), int i )
 {
    std::vector<int> v;
    
    srand( (unsigned int) time( NULL ) );
    //int i = 100000;
    
    while ( i > 0 )
    {
        v.push_back( rand() );
        --i;
    }
    
    /*printf("Before Sort\n");
    printf("Begin Vector\n");
    for ( int i = 0x0; i < v.size(); ++i )
    {
        printf("%1d ", v[i]);
    }
    printf("\nEnd Vector\n");*/
    
    printf("Begin\n");
    clock_t beginTime = clock();
    
    //sort( v.begin(), v.end(), compare );
    //quicksort( &v[0], 0, v.size() - 1 );
    //heapSort( &v[0], v.size() );
    //my_sort( &v[0], v.size() );
    //introsort( &v[0], v.size() );
    func( &v[0], v.size(), introsort_ns::greaterThan );
    
    clock_t endTime = clock();
    std::cout << "TIME: " << (endTime - beginTime) /*/ CLOCKS_PER_SEC*/ << " seconds" << std::endl;
    printf("\nDone\n");
    
    /*printf("After Sort\n");
    printf("Begin Vector\n");
    for ( size_t i = 0x0; i < v.size(); ++i )
    {
        printf("%1d ", v[i]);
    }
    printf("\nEnd Vector\n");*/
    
    for ( size_t i = 0x0; i < v.size() - 1; ++i )
    {
        assert( v[i] >= v[i + 1] );
    }
    printf("\nsize: %1d\n", v.size());
 }
 #endif // SORT_TEST_TYPE == 1

 #if SORT_TEST_TYPE == 2
 // i = number of numbers to generate and sort
 template < typename T1, typename T2 >
 void test_sort( void(*func)( T1 * const a, size_t size, T2** compareValuesList, size_t compareValuesListSize, 
                                                    bool(**compare)(const T2&, const T2&) ), int i )
 {
 
    srand( (unsigned int) time( NULL ) );
    
    std::vector<int> tempA( i );
    std::vector<int> tempB( i );
    std::vector<int> tempC( i );
    
    while ( i > 0 )
    {
        tempA.push_back( rand() );
        tempB.push_back( rand() );
        tempC.push_back( rand() );
        --i;
    }
    
    int* compareValuesList[] = { &tempB[0], &tempC[0] };
    bool (*compareList[])(const int&, const int&) = { introsort_ns::lessThan<int>, introsort_ns::greaterThan<int> };
    
    /*int a[] = { 5, 10, 2, 4, 7, 1, 8, 3, 9, 6, 11, 15, 14, 13, 12, 20, 19, 17, 18, 16 };
    int b[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
    int c[] = { 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 2, 2, 2, 1, 3 };
    //int c[] = { -5, -10, -2, -4, -7, -1, -8, -3, -9, -6, -11, -15, -14, -13, -12, -20, -19, -17, -18, -16 };
    int* compareValuesList[] = { b, c };
    bool (*compareList[])(const int&, const int&) = { introsort_ns::lessThan<int>, introsort_ns::greaterThan<int> };

    std::vector<int> v( a, a + (sizeof( a ) / sizeof( int )) );*/
    
    /*printf("Before Sort\n");
    printf("Begin Vector\n");
    for ( int i = 0x0; i < v.size(); ++i )
    {
        printf("%1d ", v[i]);
    }
    printf("\nEnd Vector\n");*/
    
    printf("Begin\n");
    clock_t beginTime = clock();

    //func( &v[0], v.size(), compareValuesList, 2, compareList );
    func( &tempA[0], tempA.size(), compareValuesList, 2, compareList );
    
    clock_t endTime = clock();
    std::cout << "TIME: " << (endTime - beginTime) /*/ CLOCKS_PER_SEC*/ << " seconds" << std::endl;
    printf("\nDone\n");
    
    /*printf("After Sort\n");
    printf("Begin Vector\n");
    for ( size_t i = 0x0; i < v.size(); ++i )
    {
        printf("%1d ", v[i]);
    }
    printf("\n");
    for ( size_t i = 0x0; i < v.size(); ++i )
    {
        printf("%1d ", b[i]);
    }
    printf("\n");
    for ( size_t i = 0x0; i < v.size(); ++i )
    {
        printf("%1d ", c[i]);
    }
    printf("\nEnd Vector\n");*/
    
    /*for ( size_t i = 0x0; i < v.size() - 1; ++i )
    {
        assert( v[i] <= v[i + 1] );
    }*/
    //printf("\nsize: %1d\n", v.size());
 }
 #endif // SORT_TEST_TYPE == 2

 // 1 2 3 4 5 6 7 8

 // 4*1 + 2*2 + 1*4


 // (n/2)*log(n)

 // 1 2 3 4 5 6 7 8 9 10 11

 // if num <= num/2, do not sort (i.e. r > size - g)

 // 5*1 + 3*2 + 2*4 + 1*8


 // a = array of elements to be sorted
 // size = number of elements in the array
 // g = comparison group index
 // r = radius of comparison
 // (e.g. if we compare (1 2) | (3 4), then r = 4)
 template <typename TYPENAME>
 static void my_sort( TYPENAME * const a, size_t size )
 {
    for ( unsigned int r = 0x2; (r / 0x2) < size; r *= 0x2 )
    {
        for ( unsigned int g = 0x0; g < size; g += r )
        {
	        if ( r <= size - g )    // if the group to sort is equal to the radius
	        {
		       my_partial_sort( a, r, g, r + g );
	        }
	        else	// r > size - g
		            // same as above, except 
		            // 1) "j < r + g" is changed to "j < size"
	        {
		        // Example for r = 4:
		        //
		        // (1 2 | 3) <-- not sorted
		        // (1 2 | 3 4) | (5)	<-- already sorted
		        // (1 2 | 3 4) | (5 7)	<-- already sorted
		        // (1 2 | 3 4) | (5 7 | 6)  <-- not sorted

		        if ( r/2 < size - g )	// if r/2 >= size - g, then this group is already sorted, so do not sort
		        {
                    my_partial_sort( a, r, g, size );
		        }
	        }
	        
	        /*printf("    While Sorting g = %1d\n", g);
            printf("    Array: ");
            for ( int i = 0x0; i < size; ++i )
            {
                printf("%1d ", a[i]);
            }
            printf("\n");*/
        }
        
        /*printf("While Sorting r = %1d\n", r);
        printf("Array: ");
        for ( int i = 0x0; i < size; ++i )
        {
            printf("%1d ", a[i]);
        }
        printf("\n");*/
    }
 }
 
 template <typename TYPENAME>
 inline void my_partial_sort( TYPENAME * const a, size_t r, size_t g, size_t end )
 {
    unsigned int split = (r / 0x2) + g;  // the split point is at the half way point of the group
    unsigned int mod = 0x0;
    for ( unsigned int i = g; i < split; ++i )
    {
        bool hasSwap = false;
        TYPENAME* x = &a[i];
        for ( unsigned int j = split + mod; j < end; ++j )
        {
	        TYPENAME* y = &a[j];
	        if ( *x > *y )//compare( *x, *y ) )
	        {
		        std::swap( *x, *y );
		        x = y; // move pointer
		        
		        // bubble down the swapped *y
		        // Example reason for bubble down:
                // r = 8
                // ( 3 23 32 41) | (-1 1 2 23)
                //
                // Result:
                // (-1 1 23 2) | (3 23 32 41)
                //
                // the 32 is swap with 23, but 23 does not bubble back down.
                // Instead, we move and check 41 next.
                y = &a[i]; // notice after the swap, *y is now at *x's original position in the array
		        for ( unsigned int k = split; k < j; ++k )
		        {
		            TYPENAME* z = &a[k];
		            if ( *y > *z ) //compare( *y, *z ) )
		            {
		                std::swap( *y, *z );
		                y = z; // move pointer
		            }
		        }
		        
		        // Example reason for ++mod:
		        // 1 5 6 7  |  2 3 4 9
		        //   x+1           x	<-- pointers
		        //
		        // We know 5 > 4, so the next pointer at x+1 (i.e. content 5), should only compare with
		        // the indexes after the location of content 4 (e.g. in this case, content 9).
		        //
		        // Result:
		        // 1 5 6 7  |  2 3 4 9
		        //   x		     y	<-- indexes and pointers
		        ++mod; // if swap, then next number do numberOfComparison - 1 (i.e. 1 less comparison)
		        hasSwap = true;
	        }
	        else
		    {
		            break; // if *x <= *y, then *x is less than or equal to all subsequent *y
		    }
		    
		    /*printf("            While Sorting j = %1d\n", j);
            printf("            Array: ");
            for ( int i = 0x0; i < size; ++i )
            {
                printf("%1d ", a[i]);
            }
            printf("\n");*/
        }
        
        // if no swap took place and previous swap has occurred (i.e. mod > 0)
        if ( !hasSwap && mod > 0 )
        {
	        // Example reason for the swaps below:
	        // r = 4
	        // 1 5 6 7  |  2 3 4   9
	        //   x             x-1 y	<-- indexes and pointers
	        //
	        // Result:
	        // 1 2 6 7  |  3 4 5 9
	        //		   x j	<-- indexes and pointers
	        for ( unsigned int k = split; k < split + mod; ++k )
	        {
		        TYPENAME* y = &a[k];
		        std::swap( *x, *y );
		        x = y; // move pointer
	        }
        }
        
        /*printf("        While Sorting i = %1d\n", i);
        printf("        Array: ");
        for ( int i = 0x0; i < size; ++i )
        {
            printf("%1d ", a[i]);
        }
        printf("\n");*/
    }
 }
 
/**
 * quicksort() sorts the specified array from the specified start to end index
 * in ascending order.
 *
 * @param (TYPENAME *)arrayPtr, (size_t)start, (size_t)end
 */
 template < typename TYPENAME >
void quicksort( TYPENAME *arrayPtr, size_t start, size_t end )
{
	TYPENAME midpoint = partition( arrayPtr, start, end );

	if ( start != midpoint )
	{ 
		quicksort( arrayPtr, start, midpoint - 1 );
	}
	if ( end != midpoint )
	{
		quicksort( arrayPtr, midpoint + 1, end );
	}
}

/**
 * partition() takes the element of the specified array located at the specified start 
 * index and place it in the array location such that all elements before it are less 
 * than it, while all elements after it are greater than it.
 *
 * @param (TYPENAME *)arrayPtr, (size_t)start, (size_t)end
 * @return size_t
 */
 template < typename TYPENAME >
size_t partition( TYPENAME *arrayPtr, size_t start, size_t end )
{
	TYPENAME element = arrayPtr[start];

	while ( start != end )
	{
		for ( ; element <= arrayPtr[end]; --end )
		{
			if ( start == end )
			{
				return start;
			}
		}
		swap( arrayPtr[start], arrayPtr[end] );
		++start;

		for ( ; element >= arrayPtr[start]; ++start )
		{
			if ( start == end )
			{
				return start;
			}
		}
		swap( arrayPtr[start], arrayPtr[end] );
		--end;
	}

	return start; // the location where the element is located
}

/**
 * swap() switches the specified first element with the specified second element
 *
 * @param (TYPENAME&)element1, (TYPENAME&)element2
 */
template < typename TYPENAME >
void swap( TYPENAME &element1, TYPENAME &element2 )
{
	TYPENAME hold = element1;
	element1 = element2;
	element2 = hold;
}

 template < typename TYPENAME >
 void heapSort(TYPENAME* numbers, size_t array_size)
 {
    TYPENAME temp;
    size_t i;

    for (i = (array_size < 0x2 ? 0x0 : (array_size >> 0x1)-1); i >= 0x0; --i)
    {
        siftDown(numbers, i, array_size);
    
        if ( i == 0 )
            break;
    }

    for (i = (array_size < 0x1 ? 0x0 : array_size-1); i >= 0x1; --i)
    {
        temp = numbers[0];
        numbers[0] = numbers[i];
        numbers[i] = temp;
        siftDown(numbers, 0, i-1);
    }
 }

 template < typename TYPENAME >
 void siftDown(TYPENAME* numbers, size_t root, size_t bottom)
 {
    bool done( false );
    size_t maxChild;
    TYPENAME temp;
    
    while (((root << 0x1) <= bottom) && (!done))
    {
        if ((root << 0x1) == bottom)
            maxChild = (root << 0x1);
        else if (numbers[(root << 0x1)] > numbers[(root << 0x1) + 1])
            maxChild = (root << 0x1);
        else
            maxChild = (root << 0x1) + 1;

        if (numbers[root] < numbers[maxChild])
        {
            temp = numbers[root];
            numbers[root] = numbers[maxChild];
            numbers[maxChild] = temp;
            root = maxChild;
        }
        else
            done = true;
    }
 }
 
 template < typename TYPENAME >
 void binary_heapsort(TYPENAME* a, size_t array_size)
 {
    TYPENAME temp;
    size_t i;
    
    // heaplify
    // Notice: (array_size - 0x2) >> 0x1 is the index of the parent of the last element
    for (i = (array_size < 0x4 ? 0x0 : (array_size - 0x2) >> 0x1); i >= 0x0; --i)
    {
        binary_siftdown(a, i, array_size);
    
        if ( i == 0 )
            break;
    }

    for (i = (array_size < 0x2 ? 0x0 : array_size - 1); i > 0x0; --i)
    {
        // Move the top element to the bottom
        // sift down only those elements not at the bottom (i.e. element 0 to element i-1)
        temp = a[0];
        a[0] = a[i]; // move last element to the top
        a[i] = temp; // move first element to the bottom
        binary_siftdown(a, 0, i-1);
    }
 }
 
 template < typename TYPENAME >
 void binary_siftdown(TYPENAME* a, size_t root, size_t bottom)
 {
    bool done( false );
    size_t maxChild;
    TYPENAME temp;
    
    while (((root << 0x1) + 1 <= bottom) && (!done))
    {
        if ((root << 0x1) + 1 == bottom) // there is only 1 child
            maxChild = (root << 0x1) + 1;
        else if (a[(root << 0x1) + 1] > a[(root << 0x1) + 2])
            maxChild = (root << 0x1) + 1;
        else
            maxChild = (root << 0x1) + 2;

        if (a[root] < a[maxChild])
        {
            temp = a[root];
            a[root] = a[maxChild];
            a[maxChild] = temp;
            root = maxChild;
        }
        else
            done = true;
    }
 }
 
 /*template < typename TYPENAME >
 void siftDown(TYPENAME* numbers, size_t root, size_t bottom)
 {
    bool done( false );
    size_t maxChild;
    TYPENAME temp;

    size_t first_child( root << 0x1 ); // first-child index
    
    while ((first_child <= bottom) && (!done))
    {
        if (first_child == bottom)  // there is only 1 child
            maxChild = first_child;
        else if (numbers[first_child] > numbers[first_child + 1])
            maxChild = first_child;
        else
            maxChild = first_child + 1;

        if (numbers[root] < numbers[maxChild])
        {
            temp = numbers[root];
            numbers[root] = numbers[maxChild];
            numbers[maxChild] = temp;
            root = maxChild;
            first_child = root << 0x1;
        }
        else
            done = true;
    }
 }*/

 template < typename TYPENAME >
 void tertiary_heapsort(TYPENAME* a, size_t array_size)
 {
    TYPENAME temp;
    size_t i;
    
    // heaplify
    for (i = (array_size < 0x5 ? 0x0 : (array_size - 0x2) / 0x3); i >= 0x0; --i)
    {
        tertiary_siftdown(a, i, array_size);
    
        if ( i == 0 )
            break;
    }

    for (i = (array_size < 0x2 ? 0x0 : array_size - 1); i > 0x0; --i)
    {
        // Move the top element to the back
        // sift down only those elements not in the back (i.e. element 0 to element i-1)
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        tertiary_siftdown(a, 0, i-1);
    }
 }

 /*template < typename TYPENAME >
 void tertiary_siftdown(TYPENAME* numbers, size_t root, size_t bottom)
 {
    bool done( false );
    size_t maxChild;
    TYPENAME temp;

    size_t first_child( root * 0x3 ); // first child index
    
    while ((first_child <= bottom) && (!done))
    {
        if (first_child == bottom) // there is only 1 child
            maxChild = first_child;
        else if (numbers[first_child] > numbers[first_child + 1])
        {
            if ( first_child + 2 <= bottom )
            {
                if ( numbers[first_child] > numbers[first_child + 2] )
                    maxChild = first_child;
                else // numbers[first_child] <= numbers[first_child + 2]
                    maxChild = first_child + 2;
            }
            else
                maxChild = first_child;
        }
        else if ( first_child + 2 <= bottom )
        {
            if ( numbers[first_child + 1] > numbers[first_child + 2] )
                maxChild = first_child + 1;
            else // numbers[first_child + 1] <= numbers[first_child + 2]
                maxChild = first_child + 2;
        }
        else
            maxChild = first_child + 1;

        if (numbers[root] < numbers[maxChild])
        {
            temp = numbers[root];
            numbers[root] = numbers[maxChild];
            numbers[maxChild] = temp;
            root = maxChild;
            first_child = root * 0x3;
        }
        else
            done = true;
    }
 }*/
 
 template < typename TYPENAME >
 void tertiary_siftdown(TYPENAME* a, size_t root, size_t bottom)
 {
    bool done( false );
    size_t maxChild;
    TYPENAME temp;

    while (((root * 0x3) + 1 <= bottom) && (!done))
    {
        if ((root * 0x3) + 1 == bottom) // there is only 1 child
            maxChild = (root * 0x3) + 1;
        else if (a[(root * 0x3) + 1] > a[(root * 0x3) + 2])
        {
            if ( (root * 0x3) + 3 <= bottom )
            {
                if ( a[(root * 0x3) + 1] > a[(root * 0x3) + 3] )
                    maxChild = (root * 0x3) + 1;
                else // a[(root * 0x3) + 1] <= a[(root * 0x3) + 3]
                    maxChild = (root * 0x3) + 3;
            }
            else
                maxChild = (root * 0x3) + 1;
        }
        else if ( (root * 0x3) + 3 <= bottom )
        {
            if ( a[(root * 0x3) + 2] > a[(root * 0x3) + 3] )
                maxChild = (root * 0x3) + 2;
            else // a[(root * 0x3) + 2] <= a[(root * 0x3) + 3]
                maxChild = (root * 0x3) + 3;
        }
        else // a[(root * 0x3) + 1] <= a[(root * 0x3) + 2]
            maxChild = (root * 0x3) + 2;

        if (a[root] < a[maxChild])
        {
            temp = a[root];
            a[root] = a[maxChild];
            a[maxChild] = temp;
            root = maxChild;
        }
        else
            done = true;
    }
 }
 
 template < typename TYPENAME >
 void biquadratic_heapsort(TYPENAME* a, size_t array_size)
 {
    TYPENAME temp;
    size_t i;
    
    // heaplify
    for (i = (array_size < 0x6 ? 0x0 : (array_size - 0x2) >> 0x2); i >= 0x0; --i)
    {
        biquadratic_siftdown(a, i, array_size);
    
        if ( i == 0 )
            break;
    }

    for (i = (array_size < 0x2 ? 0x0 : array_size - 1); i > 0x0; --i)
    {
        // Move the top element to the back
        // sift down only those elements not in the back (i.e. element 0 to element i-1)
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        biquadratic_siftdown(a, 0, i-1);
    }
 }
 
 template < typename TYPENAME >
 void biquadratic_siftdown(TYPENAME* a, size_t root, size_t bottom)
 {
    bool done( false );
    size_t maxChild;
    TYPENAME temp;

    while (((root << 0x2) + 1 <= bottom) && (!done))
    {
        if ((root << 0x2) + 1 == bottom) // there is only 1 child
            maxChild = (root << 0x2) + 1;
        else if (a[(root << 0x2) + 1] > a[(root << 0x2) + 2]) // if 1 > 2
        {
            if ( (root << 0x2) + 3 <= bottom ) // if 3 exists
            {
                if ( a[(root << 0x2) + 1] > a[(root << 0x2) + 3] ) // if 1 > 3
                {
                    if ( (root << 0x2) + 4 <= bottom ) // if 4 exists
                    {
                        if ( a[(root << 0x2) + 1] > a[(root << 0x2) + 4] ) // if 1 > 4
                            maxChild = (root << 0x2) + 1;
                        else // 4 >= 1
                            maxChild = (root << 0x2) + 4;
                    }
                    else
                        maxChild = (root << 0x2) + 1;
                }
                else // 3 >= 1
                {
                    if ( (root << 0x2) + 4 <= bottom ) // if 4 exists
                    {
                        if ( a[(root << 0x2) + 3] > a[(root << 0x2) + 4] ) // if 3 > 4
                            maxChild = (root << 0x2) + 3;
                        else // 4 >= 3
                            maxChild = (root << 0x2) + 4;
                    }
                    else
                        maxChild = (root << 0x2) + 3;
                }
            }
            else
                maxChild = (root << 0x2) + 1;
        }
        else if ( (root << 0x2) + 3 <= bottom ) // if 3 exists and 2 >= 1
        {
            if ( a[(root << 0x2) + 2] > a[(root << 0x2) + 3] ) // if 2 > 3
            {
                if ( (root << 0x2) + 4 <= bottom ) // if 4 exists
                {
                    if ( a[(root << 0x2) + 2] > a[(root << 0x2) + 4] ) // if 2 > 4
                        maxChild = (root << 0x2) + 2;
                    else // 4 >= 2
                        maxChild = (root << 0x2) + 4;
                }
                else
                    maxChild = (root << 0x2) + 2;
            }
            else // 3 >= 2
            {
                if ( (root << 0x2) + 4 <= bottom ) // if 4 exists
                {
                    if ( a[(root << 0x2) + 3] > a[(root << 0x2) + 4] ) // if 3 > 4
                        maxChild = (root << 0x2) + 3;
                    else // 4 >= 3
                        maxChild = (root << 0x2) + 4;
                }
                else
                    maxChild = (root << 0x2) + 3;
            }
        }
        else // 2 >= 1
            maxChild = (root << 0x2) + 2;

        if (a[root] < a[maxChild])
        {
            temp = a[root];
            a[root] = a[maxChild];
            a[maxChild] = temp;
            root = maxChild;
        }
        else
            done = true;
    }
 }